//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 
//输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
//
// 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
// Related Topics 数组 二分查找 分治算法 
// 👍 3912 👎 0

package leetcode.editor.cn;

//Java：寻找两个正序数组的中位数
public class MedianOfTwoSortedArrays_4 {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays_4().new Solution();
        //System.out.println(solution.findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));
        //System.out.println(solution.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));
        //System.out.println(solution.findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));
        //System.out.println(solution.findMedianSortedArrays(new int[]{}, new int[]{1}));
        //System.out.println(solution.findMedianSortedArrays(new int[]{0, 0, 0, 0, 0}, new int[]{-1, 0, 0, 0, 0, 0, 1}));
        System.out.println(solution.findMedianSortedArrays(new int[]{}, new int[]{2, 3}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len = nums1.length + nums2.length;
            int half = len / 2 + 1;
            int[] all = new int[len];
            System.arraycopy(nums1, 0, all, 0, Math.min(nums1.length, half));
            if (len == 1) {
                System.arraycopy(nums2, 0, all, nums1.length, nums2.length);
                return all[0];
            }
            if (len == 2) {
                System.arraycopy(nums2, 0, all, nums1.length, nums2.length);
                return (all[0] + all[1]) / 2.0d;
            }

            boolean isSingle = len % 2 > 0;
            f:
            for (int j = 0; j < nums2.length; j++) {
                for (int i = 0; true; i++) {
                    if (nums2[j] < all[i]) {
                        for (int k = half; k > i; k--) {
                            all[k] = all[k - 1];
                        }
                        all[i] = nums2[j];
                        break;
                    } else if (i >= nums1.length + j) {
                        all[i] = nums2[j];
                        break;
                    }
                    if (i == half) {
                        break f;
                    }
                }
            }
            if (isSingle) {
                return all[half - 1];
            } else {
                return (all[half - 1] + all[half - 2]) / 2.0d;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}